// 版权所有2016 etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package adt

import (
	"bytes"
	"fmt"
	"math"
	"strings"
)

// Compariable是三分体比较的接口。
type Comparable interface {
	// Compare给出三方比较的结果
	// a.Compare（b）=1=>a>b 
	// a.Compare（b）=0=>a==b 
	// a.Compare（b）=-1=>a<b 
	Compare(c Comparable) int
}

type rbcolor int

const (
	black rbcolor = iota
	red
)

func (c rbcolor) String() string {
	switch c {
	case black:
		return "black"
	case red:
		return "red"
	default:
		panic(fmt.Errorf("unknown color %d", c))
	}
}

// Interval实现了一个可比较的区间[begin，end]
// TODO:支持不同种类的区间：（a，b），[a，b]，（a，b]
type Interval struct {
	Begin Comparable
	End   Comparable
}

// Compare on a interval给出==如果区间重叠。
func (ivl *Interval) Compare(c Comparable) int {
	ivl2 := c.(*Interval)
	ivbCmpBegin := ivl.Begin.Compare(ivl2.Begin)
	ivbCmpEnd := ivl.Begin.Compare(ivl2.End)
	iveCmpBegin := ivl.End.Compare(ivl2.Begin)

	// ivl在ivl2的左边
	if ivbCmpBegin < 0 && iveCmpBegin <= 0 {
		return -1
	}

	// iv在iv2的右边
	if ivbCmpEnd >= 0 {
		return 1
	}

	return 0
}

type intervalNode struct {
	// iv是区间值对条目。
	iv IntervalValue
	// 所有子代节点的最大端点。
	max Comparable
	// 左右按关键字int的低端排序erval 
	left, right *intervalNode
	// 父节点是节点的直接祖先
	parent *intervalNode
	c      rbcolor
}

func (x *intervalNode) color(sentinel *intervalNode) rbcolor {
	if x == sentinel {
		return black
	}
	return x.c
}

func (x *intervalNode) height(sentinel *intervalNode) int {
	if x == sentinel {
		return 0
	}
	ld := x.left.height(sentinel)
	rd := x.right.height(sentinel)
	if ld < rd {
		return rd + 1
	}
	return ld + 1
}

func (x *intervalNode) min(sentinel *intervalNode) *intervalNode {
	for x.left != sentinel {
		x = x.left
	}
	return x
}

// 后续节点是树中的下一个顺序节点
func (x *intervalNode) successor(sentinel *intervalNode) *intervalNode {
	if x.right != sentinel {
		return x.right.min(sentinel)
	}
	y := x.parent
	for y != sentinel && x == y.right {
		x = y
		y = y.parent
	}
	return y
}

// updateMax更新节点及其祖先的最大值
func (x *intervalNode) updateMax(sentinel *intervalNode) {
	for x != sentinel {
		oldmax := x.max
		max := x.iv.Ivl.End
		if x.left != sentinel && x.left.max.Compare(max) > 0 {
			max = x.left.max
		}
		if x.right != sentinel && x.right.max.Compare(max) > 0 {
			max = x.right.max
		}
		if oldmax.Compare(max) == 0 {
			break
		}
		x.max = max
		x = x.parent
	}
}

type nodeVisitor func(n *intervalNode) bool

// visit将在与给定间隔重叠的每个节点上调用节点访问者
func (x *intervalNode) visit(iv *Interval, sentinel *intervalNode, nv nodeVisitor) bool {
	if x == sentinel {
		return true
	}
	v := iv.Compare(&x.iv.Ivl)
	switch {
	case v < 0:
		if !x.left.visit(iv, sentinel, nv) {
			return false
		}
	case v > 0:
		maxiv := Interval{x.iv.Ivl.Begin, x.max}
		if maxiv.Compare(iv) == 0 {
			if !x.left.visit(iv, sentinel, nv) || !x.right.visit(iv, sentinel, nv) {
				return false
			}
		}
	default:
		if !x.left.visit(iv, sentinel, nv) || !nv(x) || !x.right.visit(iv, sentinel, nv) {
			return false
		}
	}
	return true
}

// IntervalVvalue表示包含一个范围和一个值的范围树节点。IntervalTree表示一个（大部分）教科书实现的
type IntervalValue struct {
	Ivl Interval
	Val interface{}
}

// “算法简介”（Cormen等人，第3版）第13章红黑树
// 和第14.3章支持搜索的区间树“刺伤查询”.
type IntervalTree interface {
	// Insert将具有给定间隔的节点添加到树中。
	Insert(ivl Interval, val interface{})
	// Delete将具有给定间隔的节点从树中删除，如果确实删除了节点，则返回
	// true。
	Delete(ivl Interval) bool
	// Len给出树中的元素数。
	Len() int
	// Height是l的数目树中的级别；一个节点的高度为1。
	Height() int
	// MaxHeight是给定节点数的预期最大树高。
	MaxHeight() int
	// Visit在与给定间隔相交的每个树节点上调用visitor函数。
	// 它将访问每个间隔[x，y）按x升序排序。
	Visit(ivl Interval, ivv IntervalVisitor)
	// Find获取与给定间隔匹配的节点的IntervalValue 
	Find(ivl Interval) *IntervalValue
	// 如果有树节点与给定间隔相交，则Intersects返回true。
	Intersects(iv Interval) bool
	// 如果间隔树的键覆盖整个给定间隔，则包含返回true。
	Contains(ivl Interval) bool
	// Stab返回树中所有元素与间隔相交的切片。
	Stab(iv Interval) []*IntervalValue
	// Union将给定的间隔树合并到接收器中。
	Union(inIvt IntervalTree, ivl Interval)
}

// NewIntervalTree返回一个新的间隔树。
func NewIntervalTree() IntervalTree {
	sentinel := &intervalNode{
		iv:     IntervalValue{},
		max:    nil,
		left:   nil,
		right:  nil,
		parent: nil,
		c:      black,
	}
	return &intervalTree{
		root:     sentinel,
		count:    0,
		sentinel: sentinel,
	}
}

type intervalTree struct {
	root  *intervalNode
	count int

	// 红黑零节点
	// 使用“sentinel”作为虚拟对象简化边界条件tions 
	// 使用sentinel将节点x的nil子节点视为其父节点为x的普通节点
	// 使用一个共享sentinel表示所有nil叶子和根的父节点
	sentinel *intervalNode
}

// TODO:使其与教科书实现
// 
// “算法简介”（Cormen等人，第3版），第13.4章，第324页
// 
// 0.RB-DELETE（T，z）
// 1.
// 2.y=z 
// 3.y-original-color=y.color 
// 4.
// 5.if z.left==T.nil 
// 8.如果z.right==T.nil 
// 9.x=z.left 
// 10.RB-TRANSPLANT（T，z，z.left）
// 11.否则
// 12.y=TREE-MINIMUM（z.right）
// 13.y-original-color=y.color 
// 14.x=y.right 
// 15.如果y.p==z 
// 16.x.p=y 
// 17.其他
// 18.RB-TRANSPLANT（T，y，y.right）
// 19.y.right=z.right 
// 21.RB-移植（T，z，y）
// 22.y.left=z.left 
// 	24. y.color=z.color 
// 25。
// 26。如果y-original-color==黑色
// 27。RB-DELETE-FIXUP（T，x）

// DELETE从树中删除具有给定间隔的节点，如果确实删除了节点，则返回
// true。
func (ivt *intervalTree) Delete(ivl Interval) bool {
	z := ivt.find(ivl)
	if z == ivt.sentinel {
		return false
	}

	y := z
	if z.left != ivt.sentinel && z.right != ivt.sentinel {
		y = z.successor(ivt.sentinel)
	}

	x := ivt.sentinel
	if y.left != ivt.sentinel {
		x = y.left
	} else if y.right != ivt.sentinel {
		x = y.right
	}

	x.parent = y.parent

	if y.parent == ivt.sentinel {
		ivt.root = x
	} else {
		if y == y.parent.left {
			y.parent.left = x
		} else {
			y.parent.right = x
		}
		y.parent.updateMax(ivt.sentinel)
	}
	if y != z {
		z.iv = y.iv
		z.updateMax(ivt.sentinel)
	}

	if y.color(ivt.sentinel) == black {
		ivt.deleteFixup(x)
	}

	ivt.count--
	return true
}

// “算法简介”（Cormen等人，第三版），第13.4章，第26页
// 
// 0。RB-DELETE-FIXUP（T，z）
// 1。
// 2。而x≠ T.root和x.color==黑色
// 3。如果x==x.p.left 
// 4。w=x.p.右
// 5。如果w.color==红色
// 6。w.color=黑色
// 7。x.p.color=红色
// 8。左旋转（T，x，p）
// 9。如果w向左。颜色==黑色，右侧为w。颜色==黑色
// 10。w.color=红色
// 11。x=x.p 
// 12。否则，如果w是对的。颜色==黑色
// 13。w.左。颜色=黑色
// 14。w.color=红色
// 15。右旋转（T，w）
// 16。w=w.p.右
// 17。w.color=x.p.color 
// 18。x.p.color=黑色
// 19。左旋转（T，w.p）
// 20。x=T.root 
// 21。否则
// 22。w=x.p.左
// 23。如果w.color==红色
// 24。w.color=黑色
// 25。x.p.color=红色
// 26。右旋转（T，x，p）
// 27。如果是的话。颜色==黑色和w向左。颜色==黑色
// 28。w.color=红色
// 29。x=x.p 
// 30。否则，如果w离开。颜色==黑色
// 31。对。颜色=黑色
// 32。w.color=红色
// 33。左旋转（T，w）
// 34。w=w.p.左
// 35。w.color=x.p.color 
// 36。x.p.color=黑色
// 37。右旋转（T，w.p）
// 38。x=T.root 
// 39。
// 40。x、 color=黑色
// 
func (ivt *intervalTree) deleteFixup(x *intervalNode) {
	for x != ivt.root && x.color(ivt.sentinel) == black {
		if x == x.parent.left { // 第3-20行
			w := x.parent.right
			if w.color(ivt.sentinel) == red {
				w.c = black
				x.parent.c = red
				ivt.rotateLeft(x.parent)
				w = x.parent.right
			}
			if w == nil {
				break
			}
			if w.left.color(ivt.sentinel) == black && w.right.color(ivt.sentinel) == black {
				w.c = red
				x = x.parent
			} else {
				if w.right.color(ivt.sentinel) == black {
					w.left.c = black
					w.c = red
					ivt.rotateRight(w)
					w = x.parent.right
				}
				w.c = x.parent.color(ivt.sentinel)
				x.parent.c = black
				w.right.c = black
				ivt.rotateLeft(x.parent)
				x = ivt.root
			}
		} else { // 第22-38行
			// 同上，但左右交换
			w := x.parent.left
			if w.color(ivt.sentinel) == red {
				w.c = black
				x.parent.c = red
				ivt.rotateRight(x.parent)
				w = x.parent.left
			}
			if w == nil {
				break
			}
			if w.left.color(ivt.sentinel) == black && w.right.color(ivt.sentinel) == black {
				w.c = red
				x = x.parent
			} else {
				if w.left.color(ivt.sentinel) == black {
					w.right.c = black
					w.c = red
					ivt.rotateLeft(w)
					w = x.parent.left
				}
				w.c = x.parent.color(ivt.sentinel)
				x.parent.c = black
				w.left.c = black
				ivt.rotateRight(x.parent)
				x = ivt.root
			}
		}
	}

	if x != nil {
		x.c = black
	}
}

func (ivt *intervalTree) createIntervalNode(ivl Interval, val interface{}) *intervalNode {
	return &intervalNode{
		iv:     IntervalValue{ivl, val},
		max:    ivl.End,
		c:      red,
		left:   ivt.sentinel,
		right:  ivt.sentinel,
		parent: ivt.sentinel,
	}
}

// TODO:使其与教科书实现
// 
// /“算法简介”（Cormen等人，第三版），第13.3章，第315页
// 
// 0。RB-INSERT（T，z）
// 1。
// 2。y=T.nil 
// 3。x=T.root 
// 4。
// 5。而x≠ T.nil 
// 6。y=x 
// 7。如果z.key<x.key 
// 8。x=x。左
// 9。否则
// 10。x=x。右
// 11。
// 12。z、 p=y 
// 13。
// 14。如果y==T.nil 
// 15。T.root=z 
// 16。否则，如果z.key<y.key 
// 17。y.left=z 
// 18。否则
// 19。y.right=z 
// 20。
// 21。z、 左=T.nil 
// 22。z、 右=T.nil 
// 23。z、 颜色=红色
// 24。
// 25。RB-INSERT-FIXUP（T，z）

// INSERT将具有给定间隔的节点添加到树中。
func (ivt *intervalTree) Insert(ivl Interval, val interface{}) {
	y := ivt.sentinel
	z := ivt.createIntervalNode(ivl, val)
	x := ivt.root
	for x != ivt.sentinel {
		y = x
		if z.iv.Ivl.Begin.Compare(x.iv.Ivl.Begin) < 0 {
			x = x.left
		} else {
			x = x.right
		}
	}

	z.parent = y
	if y == ivt.sentinel {
		ivt.root = z
	} else {
		if z.iv.Ivl.Begin.Compare(y.iv.Ivl.Begin) < 0 {
			y.left = z
		} else {
			y.right = z
		}
		y.updateMax(ivt.sentinel)
	}
	z.c = red

	ivt.insertFixup(z)
	ivt.count++
}

// “算法简介”（Cormen等人，第三版），第13.3章，第316页
// 
// 0。RB-INSERT-FIXUP（T，z）
// 1。
// 2。而z.p.color==红色
// 3。如果z.p==z.p.p.left 
// 4。y=z.p.p.右
// 5。如果y.color==红色
// 6。z.p.color=黑色
// 7。y.color=黑色
// 8。z.p.p.color=红色
// 9。z=z.p.p 
// 10。如果z==z.p.right 
// 11，则为else。z=z.p 
// 12。左旋转（T，z）
// 13。z.p.color=黑色
// 14。z.p.p.color=红色
// 15。右旋转（T，z.p.p）
// 16。否则
// 17。y=z.p.p.左
// 18。如果y.color==红色
// 19。z.p.color=黑色
// 20。y.color=黑色
// 21。z.p.p.color=红色
// 22。z=z.p.p 
// 23。如果z==z.p.right 
// 24，则为else。z=z.p 
// 25。右旋转（T，z）
// 26。z.p.color=黑色
// 27。z.p.p.color=红色
// 28。左旋转（T，z.p.p）
// 29。
// 30。草根。颜色=黑色
// 
func (ivt *intervalTree) insertFixup(z *intervalNode) {
	for z.parent.color(ivt.sentinel) == red {
		if z.parent == z.parent.parent.left { // 第3-15行

			y := z.parent.parent.right
			if y.color(ivt.sentinel) == red {
				y.c = black
				z.parent.c = black
				z.parent.parent.c = red
				z = z.parent.parent
			} else {
				if z == z.parent.right {
					z = z.parent
					ivt.rotateLeft(z)
				}
				z.parent.c = black
				z.parent.parent.c = red
				ivt.rotateRight(z.parent.parent)
			}
		} else { // 第16-28行
			// 与左/右交换
			y := z.parent.parent.left
			if y.color(ivt.sentinel) == red {
				y.c = black
				z.parent.c = black
				z.parent.parent.c = red
				z = z.parent.parent
			} else {
				if z == z.parent.left {
					z = z.parent
					ivt.rotateRight(z)
				}
				z.parent.c = black
				z.parent.parent.c = red
				ivt.rotateLeft(z.parent.parent)
			}
		}
	}

	// 第30行
	ivt.root.c = black
}

// 旋转左移x，使其位于其右子代
// 
// “算法简介”（Cormen等人，第3版），第13.2章，p313 
// 
// 0。左旋转（T，x）
// 1。
// 2。y=x。右
// 3。x、 右=y。左
// 4。
// 5。如果你离开了≠ T.nil 
// 6。是的，左边。p=x 
// 7。
// 8。y、 p=x.p 
// 9。
// 10。如果x.p==T.nil 
// 11。T.root=y 
// 12。如果x==x.p.left 
// 13，则为else。x.p.left=y 
// 14。否则
// 15。x.p.right=y 
// 16。
// 17。y、 左=x 
// 18。x、 p=y 
// 
func (ivt *intervalTree) rotateLeft(x *intervalNode) {
	// rotateLeft x必须有右子
	if x.right == ivt.sentinel {
		return
	}

	// 2-3行
	y := x.right
	x.right = y.left

	// 5-6行
	if y.left != ivt.sentinel {
		y.left.parent = x
	}
	x.updateMax(ivt.sentinel)

	// 10-15行，18行
	ivt.replaceParent(x, y)

	// 17行
	y.left = x
	y.updateMax(ivt.sentinel)
}

// rotateRight移动x，使其位于左子
// 
// 1。
// 2。y=x.左
// 3。x、 左=y。右
// 4。
// 5。如果你是对的≠ T.nil 
// 6。是的。p=x 
// 7。
// 8。y、 p=x.p 
// 9。
// 10。如果x.p==T.nil 
// 11。T.root=y 
// 12。如果x==x.p.right 
// 13，则为else。x.p.right=y 
// 14。否则
// 15。x.p.left=y 
// 16。
// 17。y、 右=x 
// 18。x、 p=y 
// 
func (ivt *intervalTree) rotateRight(x *intervalNode) {
	// 旋转右x必须有左子
	if x.left == ivt.sentinel {
		return
	}

	// 第2-3行
	y := x.left
	x.left = y.right

	// 第5-6行
	if y.right != ivt.sentinel {
		y.right.parent = x
	}
	x.updateMax(ivt.sentinel)

	// 第10-15行，18 
	ivt.replaceParent(x, y)

	// 第17行
	y.right = x
	y.updateMax(ivt.sentinel)
}

// replaceParent将x的父级替换为y 
func (ivt *intervalTree) replaceParent(x *intervalNode, y *intervalNode) {
	y.parent = x.parent
	if x.parent == ivt.sentinel {
		ivt.root = y
	} else {
		if x == x.parent.left {
			x.parent.left = y
		} else {
			x.parent.right = y
		}
		x.parent.updateMax(ivt.sentinel)
	}
	x.parent = y
}

// Len给出树中的元素数
func (ivt *intervalTree) Len() int { return ivt.count }

// Height是树中的层数；一个节点的高度为1。
func (ivt *intervalTree) Height() int { return ivt.root.height(ivt.sentinel) }

// MaxHeight是给定节点数的预期最大树高
func (ivt *intervalTree) MaxHeight() int {
	return int((2 * math.Log2(float64(ivt.Len()+1))) + 0.5)
}

// IntervalVisitor用于树搜索；返回false以停止搜索。
type IntervalVisitor func(n *IntervalValue) bool

// Visit在与给定间隔相交的每个树节点上调用一个visitor函数。
// 它将访问每个间隔[x，y）按升序在x上排序。
func (ivt *intervalTree) Visit(ivl Interval, ivv IntervalVisitor) {
	ivt.root.visit(&ivl, ivt.sentinel, func(n *intervalNode) bool { return ivv(&n.iv) })
}

// 查找给定间隔的确切节点
func (ivt *intervalTree) find(ivl Interval) *intervalNode {
	ret := ivt.sentinel
	f := func(n *intervalNode) bool {
		if n.iv.Ivl != ivl {
			return true
		}
		ret = n
		return false
	}
	ivt.root.visit(&ivl, ivt.sentinel, f)
	return ret
}

// find获取与给定间隔匹配的节点的IntervalValue 
func (ivt *intervalTree) Find(ivl Interval) (ret *IntervalValue) {
	n := ivt.find(ivl)
	if n == ivt.sentinel {
		return nil
	}
	return &n.iv
}

// 如果有树节点与给定间隔相交，则Intersects返回true。
func (ivt *intervalTree) Intersects(iv Interval) bool {
	x := ivt.root
	for x != ivt.sentinel && iv.Compare(&x.iv.Ivl) != 0 {
		if x.left != ivt.sentinel && x.left.max.Compare(iv.Begin) > 0 {
			x = x.left
		} else {
			x = x.right
		}
	}
	return x != ivt.sentinel
}

// 如果interval树的键覆盖整个给定间隔。
func (ivt *intervalTree) Contains(ivl Interval) bool {
	var maxEnd, minBegin Comparable

	isContiguous := true
	ivt.Visit(ivl, func(n *IntervalValue) bool {
		if minBegin == nil {
			minBegin = n.Ivl.Begin
			maxEnd = n.Ivl.End
			return true
		}
		if maxEnd.Compare(n.Ivl.Begin) < 0 {
			isContiguous = false
			return false
		}
		if n.Ivl.End.Compare(maxEnd) > 0 {
			maxEnd = n.Ivl.End
		}
		return true
	})

	return isContiguous && minBegin != nil && maxEnd.Compare(ivl.End) >= 0 && minBegin.Compare(ivl.Begin) <= 0
}

// Stab返回树中所有元素与间隔相交的切片。
func (ivt *intervalTree) Stab(iv Interval) (ivs []*IntervalValue) {
	if ivt.count == 0 {
		return nil
	}
	f := func(n *IntervalValue) bool { ivs = append(ivs, n); return true }
	ivt.Visit(iv, f)
	return ivs
}

// Union将给定间隔树合并到接收器中。
func (ivt *intervalTree) Union(inIvt IntervalTree, ivl Interval) {
	f := func(n *IntervalValue) bool {
		ivt.Insert(n.Ivl, n.Val)
		return true
	}
	inIvt.Visit(ivl, f)
}

type visitedInterval struct {
	root  Interval
	left  Interval
	right Interval
	color rbcolor
	depth int
}

func (vi visitedInterval) String() string {
	bd := new(strings.Builder)
	bd.WriteString(fmt.Sprintf("root [%v,%v,%v], left [%v,%v], right [%v,%v], depth %d",
		vi.root.Begin, vi.root.End, vi.color,
		vi.left.Begin, vi.left.End,
		vi.right.Begin, vi.right.End,
		vi.depth,
	))
	return bd.String()
}

// visitLevel按级别顺序遍历树。
// 用于测试
func (ivt *intervalTree) visitLevel() []visitedInterval {
	if ivt.root == ivt.sentinel {
		return nil
	}

	rs := make([]visitedInterval, 0, ivt.Len())

	type pair struct {
		node  *intervalNode
		depth int
	}
	queue := []pair{{ivt.root, 0}}
	for len(queue) > 0 {
		f := queue[0]
		queue = queue[1:]

		vi := visitedInterval{
			root:  f.node.iv.Ivl,
			color: f.node.color(ivt.sentinel),
			depth: f.depth,
		}
		if f.node.left != ivt.sentinel {
			vi.left = f.node.left.iv.Ivl
			queue = append(queue, pair{f.node.left, f.depth + 1})
		}
		if f.node.right != ivt.sentinel {
			vi.right = f.node.right.iv.Ivl
			queue = append(queue, pair{f.node.right, f.depth + 1})
		}

		rs = append(rs, vi)
	}

	return rs
}

type StringComparable string

func (s StringComparable) Compare(c Comparable) int {
	sc := c.(StringComparable)
	if s < sc {
		return -1
	}
	if s > sc {
		return 1
	}
	return 0
}

func NewStringInterval(begin, end string) Interval {
	return Interval{StringComparable(begin), StringComparable(end)}
}

func NewStringPoint(s string) Interval {
	return Interval{StringComparable(s), StringComparable(s + "\x00")}
}

// StringAffingeComparable将“”视为>所有其他字符串
type StringAffineComparable string

func (s StringAffineComparable) Compare(c Comparable) int {
	sc := c.(StringAffineComparable)

	if len(s) == 0 {
		if len(sc) == 0 {
			return 0
		}
		return 1
	}
	if len(sc) == 0 {
		return -1
	}

	if s < sc {
		return -1
	}
	if s > sc {
		return 1
	}
	return 0
}

func NewStringAffineInterval(begin, end string) Interval {
	return Interval{StringAffineComparable(begin), StringAffineComparable(end)}
}

func NewStringAffinePoint(s string) Interval {
	return NewStringAffineInterval(s, s+"\x00")
}

func NewInt64Interval(a int64, b int64) Interval {
	return Interval{Int64Comparable(a), Int64Comparable(b)}
}

func newInt64EmptyInterval() Interval {
	return Interval{Begin: nil, End: nil}
}

func NewInt64Point(a int64) Interval {
	return Interval{Int64Comparable(a), Int64Comparable(a + 1)}
}

type Int64Comparable int64

func (v Int64Comparable) Compare(c Comparable) int {
	vc := c.(Int64Comparable)
	cmp := v - vc
	if cmp < 0 {
		return -1
	}
	if cmp > 0 {
		return 1
	}
	return 0
}

// BytesAffineComparable将空字节数组视为>所有其他字节数组
type BytesAffineComparable []byte

func (b BytesAffineComparable) Compare(c Comparable) int {
	bc := c.(BytesAffineComparable)

	if len(b) == 0 {
		if len(bc) == 0 {
			return 0
		}
		return 1
	}
	if len(bc) == 0 {
		return -1
	}

	return bytes.Compare(b, bc)
}

func NewBytesAffineInterval(begin, end []byte) Interval {
	return Interval{BytesAffineComparable(begin), BytesAffineComparable(end)}
}

func NewBytesAffinePoint(b []byte) Interval {
	be := make([]byte, len(b)+1)
	copy(be, b)
	be[len(b)] = 0
	return NewBytesAffineInterval(b, be)
}
